# leetcode 257 二叉树所有路径

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:

        path = [] # 储存单条路径
        result= [] # 储存最后结果

        def get_path(node):
            path.append(node.val)
            if node.left is None and node.right is None:
                result.append("->".join(map(str, path)))
                return
            if node.left:
                get_path(node.left) # 递归
                path.pop() # 回溯
            if node.right:
                get_path(node.right)
                path.pop()
        get_path(root)
        return result
